package cg.studio.algorithm.graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class GraphTypicalImpl implements Graph
{
  private Set< Edge > edges = new HashSet<Edge>();
  private Map< Point, Set<Point> > pointMap = null;
  
  public void addEdge( Edge edge )
  {
    edges.add( edge );
  }


  public Route getOneRoute( Point start, Point end )
  {
    buildPointMap();
    Stack< Point > routeStack = new Stack<Point>();
    routeStack.add( start );
    boolean haveRoute = getOneRoute( start, end, routeStack );
    if( !haveRoute )
      return null;
    
    return getRouteFromPointList( routeStack );
    
  }
  
  /**
   * Logic: can handle loop
   * - use the Stack: 
   * assume it's a route, put the point, if reach the end, return true; 
   * if not, pop out point and try another route )
   *   1. if start point connect to the end point, return true
   *   2. if no any point connect to the start point, return false
   *   3. start from start point, put start point into the stack( assume this is the route ),
   *      for each point which connect to the start, 
   *        set start ::= point, 
   *        remove the edge ( from start to this point ) to get rid of loop.
   *          if this point has route to the end, return this route.
   *          else, pop out the point from stack( recover the environment for next point )
   *          
   * - use link list: take advantage of recursive function
   * assume it is a route, go through it, if reach the end, put ( start, end ) into linked list and return true.
   * after return to the caller, caller put ( start ) in the head of the linked list.
   * 
   * @param start
   * @param end
   * @param routeStack
   * @return
   */
  protected boolean getOneRoute( Point start, Point end, Stack<Point> routeStack )
  {
    Set<Point> points = getConnectedPoints( start );
    if( points.contains( end ) )
    {
      routeStack.add( end );
      return true;
    }
    for( Point point : points )
    {
      routeStack.add( point );
      removeEdgeFromMap( start, point );
      if( getOneRoute( point, end, routeStack ) )
        return true;
      routeStack.pop();
    }
    return false;
  }
  
  protected void buildPointMap()
  {
    if( pointMap == null )
    {
      pointMap = new HashMap< Point, Set<Point> >();
    }
    else
      pointMap.clear();
  
    for( Edge edge : edges )
    {
      Set< Point > ends = pointMap.get( edge.start );
      if( ends == null )
      {
        ends = new HashSet<Point>();
        pointMap.put( edge.start, ends );
      }
      ends.add( edge.end );
    }
  }
  
  protected void removeEdgeFromMap( Point start, Point end )
  {
    Set< Point > ends = pointMap.get( start );
    ends.remove( end );
  }
  
  
  protected Set<Point> getConnectedPoints( Point start )
  {
    return pointMap.get( start );
  }
  
  protected Edge getEdge( Point start, Point end )
  {
    for( Edge edge : edges )
    {
      if( edge.start.equals( start ) && edge.end.equals( end ) )
        return edge;
    }
    return null;
  }
  
  protected Route getRouteFromPointList( Collection<Point> points )
  {
    Route route = new Route();
    Point prePoint = null;
    for( Point point : points )
    {
      if( prePoint != null )
      {
        Edge edge = getEdge( prePoint, point );
        if( edge == null )
          throw new IllegalArgumentException( "can't get edge from " + prePoint + " to " + point );
        route.addEdge( edge );
      }
      prePoint = point;
    }
    return route;
  }
  
  public Route[] getRoutes( Point start, Point end )
  {
    //buildPointMap();
    List< List<Point> > pointsList = getAllRoutes( start, end );
    if( pointsList == null || pointsList.size() == 0 )
      return null;
    
    Route[] routes = new Route[ pointsList.size() ];
    for( int i=0; i<pointsList.size(); ++i )
    {
      routes[i] = getRouteFromPointList( pointsList.get( i ) );
    }

    return routes;
  }
  
  //go through end to start;
  protected List< List<Point> > getAllRoutes( Point start, Point end )
  {
    buildPointMap();
    
    Set<Point> points = getConnectedPoints( start );
    if( points == null || points.isEmpty() )
      return null;
    
    List< List<Point> > routes = new ArrayList< List<Point> >();
    if( points.contains( end ) )
    {
      LinkedList< Point > route = new LinkedList< Point >();
      route.add( start );
      route.add( end );
      
      routes.add( route );
      
      points.remove( end );
    }
    
    if( points.isEmpty() )
    {
      return routes;
    }
  
    for( Point point : points )
    {
      List<List<Point> > subRoutes = getAllRoutes( point, end );
      if( subRoutes != null )
      {
        for( List<Point> route : subRoutes )
        {
          //insert to the head
          route.add( 0, start );  
        }
        routes.addAll( subRoutes );
      }

    }
    return routes;
  }
  
  /**
   * One method to get ShortestJumpRoute is getting all routes and then pick the shortest one
   * the other one is pretty like the broad traverse, check the points connected to start, and go deep until reach end.
   */
  public Route getShortestJumpRoute( final Point start, final Point end )
  {
    buildPointMap();

    int deepth = 0;
    Set<Point> prePoints = new HashSet<Point>();
    prePoints.add( start );
    boolean hasRoute = false;
    //make a map to keep the information Deepth => Set< Point >, the start and end point will not go to the map
    Map< Integer, Set<Point> > steps = new HashMap< Integer, Set<Point> >(); 
    while(true)
    {
      Set<Point> points = new HashSet<Point>();
      for( Point point : prePoints )
      {
        points.addAll( getConnectedPoints( point ) );  
      }
       
      if( points == null || points.isEmpty() )
        break;
      if( points.contains( end ) )
      {
        hasRoute = true;
        break;
      }
      
      //keep environment;
      steps.put( ++deepth, points );

      //for next loop
      prePoints = points;
    }
    
    if( !hasRoute )
      return null;
    
    //build the route 
    return buildRoute( start, end, steps, deepth );
  }
  
  /**
   * the steps don't includes start and end.
   * as the steps were built from start to end. it's more efficient to build route from end to start
   * @param start
   * @param end
   * @param steps
   * @return
   */
  protected Route buildRoute( Point start, Point end, Map< Integer, Set<Point> > steps, int deepth )
  {
    Route route = new Route();
    Point toPoint = end;
    for( ; deepth > 0; --deepth )
    {
      Set< Point > fromPoints = steps.get( deepth );
      for( Point fromPoint : fromPoints )
      {
        Edge edge = getEdge( fromPoint, toPoint );
        if( edge == null )
          continue;

        //this is the edge;
        route.insertEdge( edge, 0 );
        //next loop
        toPoint = fromPoint;
        break;
      }
    }

    //add the start point
    Edge edge = getEdge( start, toPoint );
    route.insertEdge( edge, 0 );
    return route;
  }
  
  public Route getShortestRoute( Point start, Point end )
  {
    // TODO Auto-generated method stub
    return null;
  }

}
